/*
 * Copyright (C) 2005, 2007, 2010 Apple Inc. All rights reserved.
 * Copyright (C) 2011 Google Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
 * THE POSSIBILITY OF SUCH DAMAGE.
 */

#include "flutter/sky/engine/core/rendering/break_lines.h"

#include "flutter/sky/engine/platform/text/TextBreakIterator.h"
#include "flutter/sky/engine/wtf/ASCIICType.h"
#include "flutter/sky/engine/wtf/StdLibExtras.h"
#include "flutter/sky/engine/wtf/unicode/CharacterNames.h"

namespace blink {

template <bool treatNoBreakSpaceAsBreak>
static inline bool isBreakableSpace(UChar ch) {
  switch (ch) {
    case ' ':
    case '\n':
    case '\t':
      return true;
    case noBreakSpace:
      return treatNoBreakSpaceAsBreak;
    default:
      return false;
  }
}

static const UChar asciiLineBreakTableFirstChar = '!';
static const UChar asciiLineBreakTableLastChar = 127;

// Pack 8 bits into one byte
#define B(a, b, c, d, e, f, g, h)                                         \
  ((a) | ((b) << 1) | ((c) << 2) | ((d) << 3) | ((e) << 4) | ((f) << 5) | \
   ((g) << 6) | ((h) << 7))

// Line breaking table row for each digit (0-9)
#define DI \
  { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

// Line breaking table row for ascii letters (a-z A-Z)
#define AL \
  { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

#define F 0xFF

// Line breaking table for printable ASCII characters. Line breaking
// opportunities in this table are as below:
// - before opening punctuations such as '(', '<', '[', '{' after certain
// characters (compatible with Firefox 3.6);
// - after '-' and '?' (backward-compatible, and compatible with Internet
// Explorer). Please refer to <https://bugs.webkit.org/show_bug.cgi?id=37698>
// for line breaking matrixes of different browsers and the ICU standard.
static const unsigned char asciiLineBreakTable
    [][(asciiLineBreakTableLastChar - asciiLineBreakTableFirstChar) / 8 + 1] = {
        //  !  "  #  $  %  &  '  (     )  *  +  ,  -  .  /  0  1-8   9  :  ;  <
        //  =  >  ?  @     A-X      Y  Z  [  \  ]  ^  _  `     a-x      y  z  {
        //  |  }  ~  DEL
        {B(0, 0, 0, 0, 0, 0, 0, 1), B(0, 0, 0, 0, 0, 0, 0, 0), 0,
         B(0, 0, 0, 1, 0, 0, 0, 0), 0, 0, 0, B(0, 0, 1, 0, 0, 0, 0, 0), 0, 0, 0,
         B(0, 0, 1, 0, 0, 0, 0, 0)},  // !
        {B(0, 0, 0, 0, 0, 0, 0, 1), B(0, 0, 0, 0, 0, 0, 0, 0), 0,
         B(0, 0, 0, 1, 0, 0, 0, 0), 0, 0, 0, B(0, 0, 1, 0, 0, 0, 0, 0), 0, 0, 0,
         B(0, 0, 1, 0, 0, 0, 0, 0)},  // "
        {B(0, 0, 0, 0, 0, 0, 0, 1), B(0, 0, 0, 0, 0, 0, 0, 0), 0,
         B(0, 0, 0, 1, 0, 0, 0, 0), 0, 0, 0, B(0, 0, 1, 0, 0, 0, 0, 0), 0, 0, 0,
         B(0, 0, 1, 0, 0, 0, 0, 0)},  // #
        {B(0, 0, 0, 0, 0, 0, 0, 0), B(0, 0, 0, 0, 0, 0, 0, 0), 0,
         B(0, 0, 0, 0, 0, 0, 0, 0), 0, 0, 0, B(0, 0, 0, 0, 0, 0, 0, 0), 0, 0, 0,
         B(0, 0, 0, 0, 0, 0, 0, 0)},  // $
        {B(0, 0, 0, 0, 0, 0, 0, 1), B(0, 0, 0, 0, 0, 0, 0, 0), 0,
         B(0, 0, 0, 1, 0, 0, 0, 0), 0, 0, 0, B(0, 0, 1, 0, 0, 0, 0, 0), 0, 0, 0,
         B(0, 0, 1, 0, 0, 0, 0, 0)},  // %
        {B(0, 0, 0, 0, 0, 0, 0, 1), B(0, 0, 0, 0, 0, 0, 0, 0), 0,
         B(0, 0, 0, 1, 0, 0, 0, 0), 0, 0, 0, B(0, 0, 1, 0, 0, 0, 0, 0), 0, 0, 0,
         B(0, 0, 1, 0, 0, 0, 0, 0)},  // &
        {B(0, 0, 0, 0, 0, 0, 0, 0), B(0, 0, 0, 0, 0, 0, 0, 0), 0,
         B(0, 0, 0, 0, 0, 0, 0, 0), 0, 0, 0, B(0, 0, 0, 0, 0, 0, 0, 0), 0, 0, 0,
         B(0, 0, 0, 0, 0, 0, 0, 0)},  // '
        {B(0, 0, 0, 0, 0, 0, 0, 0), B(0, 0, 0, 0, 0, 0, 0, 0), 0,
         B(0, 0, 0, 0, 0, 0, 0, 0), 0, 0, 0, B(0, 0, 0, 0, 0, 0, 0, 0), 0, 0, 0,
         B(0, 0, 0, 0, 0, 0, 0, 0)},  // (
        {B(0, 0, 0, 0, 0, 0, 0, 1), B(0, 0, 0, 0, 0, 0, 0, 0), 0,
         B(0, 0, 0, 1, 0, 0, 0, 0), 0, 0, 0, B(0, 0, 1, 0, 0, 0, 0, 0), 0, 0, 0,
         B(0, 0, 1, 0, 0, 0, 0, 0)},  // )
        {B(0, 0, 0, 0, 0, 0, 0, 1), B(0, 0, 0, 0, 0, 0, 0, 0), 0,
         B(0, 0, 0, 1, 0, 0, 0, 0), 0, 0, 0, B(0, 0, 1, 0, 0, 0, 0, 0), 0, 0, 0,
         B(0, 0, 1, 0, 0, 0, 0, 0)},  // *
        {B(0, 0, 0, 0, 0, 0, 0, 1), B(0, 0, 0, 0, 0, 0, 0, 0), 0,
         B(0, 0, 0, 1, 0, 0, 0, 0), 0, 0, 0, B(0, 0, 1, 0, 0, 0, 0, 0), 0, 0, 0,
         B(0, 0, 1, 0, 0, 0, 0, 0)},  // +
        {B(0, 0, 0, 0, 0, 0, 0, 1), B(0, 0, 0, 0, 0, 0, 0, 0), 0,
         B(0, 0, 0, 1, 0, 0, 0, 0), 0, 0, 0, B(0, 0, 1, 0, 0, 0, 0, 0), 0, 0, 0,
         B(0, 0, 1, 0, 0, 0, 0, 0)},  // ,
        {B(1, 1, 1, 1, 1, 1, 1, 1), B(1, 1, 1, 1, 1, 0, 1, 0), 0,
         B(0, 1, 1, 1, 1, 1, 1, 1), F, F, F, B(1, 1, 1, 1, 1, 1, 1, 1), F, F, F,
         B(1, 1, 1, 1, 1, 1, 1, 1)},  // - Note: breaking before '0'-'9' is
                                      // handled hard-coded in
                                      // shouldBreakAfter().
        {B(0, 0, 0, 0, 0, 0, 0, 1), B(0, 0, 0, 0, 0, 0, 0, 0), 0,
         B(0, 0, 0, 1, 0, 0, 0, 0), 0, 0, 0, B(0, 0, 1, 0, 0, 0, 0, 0), 0, 0, 0,
         B(0, 0, 1, 0, 0, 0, 0, 0)},  // .
        {B(0, 0, 0, 0, 0, 0, 0, 0), B(0, 0, 0, 0, 0, 0, 0, 0), 0,
         B(0, 0, 0, 0, 0, 0, 0, 0), 0, 0, 0, B(0, 0, 0, 0, 0, 0, 0, 0), 0, 0, 0,
         B(0, 0, 0, 0, 0, 0, 0, 0)},  // /
        DI,
        DI,
        DI,
        DI,
        DI,
        DI,
        DI,
        DI,
        DI,
        DI,  // 0-9
        {B(0, 0, 0, 0, 0, 0, 0, 1), B(0, 0, 0, 0, 0, 0, 0, 0), 0,
         B(0, 0, 0, 1, 0, 0, 0, 0), 0, 0, 0, B(0, 0, 1, 0, 0, 0, 0, 0), 0, 0, 0,
         B(0, 0, 1, 0, 0, 0, 0, 0)},  // :
        {B(0, 0, 0, 0, 0, 0, 0, 1), B(0, 0, 0, 0, 0, 0, 0, 0), 0,
         B(0, 0, 0, 1, 0, 0, 0, 0), 0, 0, 0, B(0, 0, 1, 0, 0, 0, 0, 0), 0, 0, 0,
         B(0, 0, 1, 0, 0, 0, 0, 0)},  // ;
        {B(0, 0, 0, 0, 0, 0, 0, 0), B(0, 0, 0, 0, 0, 0, 0, 0), 0,
         B(0, 0, 0, 0, 0, 0, 0, 0), 0, 0, 0, B(0, 0, 0, 0, 0, 0, 0, 0), 0, 0, 0,
         B(0, 0, 0, 0, 0, 0, 0, 0)},  // <
        {B(0, 0, 0, 0, 0, 0, 0, 1), B(0, 0, 0, 0, 0, 0, 0, 0), 0,
         B(0, 0, 0, 1, 0, 0, 0, 0), 0, 0, 0, B(0, 0, 1, 0, 0, 0, 0, 0), 0, 0, 0,
         B(0, 0, 1, 0, 0, 0, 0, 0)},  // =
        {B(0, 0, 0, 0, 0, 0, 0, 1), B(0, 0, 0, 0, 0, 0, 0, 0), 0,
         B(0, 0, 0, 1, 0, 0, 0, 0), 0, 0, 0, B(0, 0, 1, 0, 0, 0, 0, 0), 0, 0, 0,
         B(0, 0, 1, 0, 0, 0, 0, 0)},  // >
        {B(0, 0, 1, 1, 1, 1, 0, 1), B(0, 1, 1, 0, 1, 0, 0, 1), F,
         B(1, 0, 0, 1, 1, 1, 0, 1), F, F, F, B(1, 1, 1, 1, 0, 1, 1, 1), F, F, F,
         B(1, 1, 1, 1, 0, 1, 1, 0)},  // ?
        {B(0, 0, 0, 0, 0, 0, 0, 0), B(0, 0, 0, 0, 0, 0, 0, 0), 0,
         B(0, 0, 0, 0, 0, 0, 0, 0), 0, 0, 0, B(0, 0, 0, 0, 0, 0, 0, 0), 0, 0, 0,
         B(0, 0, 0, 0, 0, 0, 0, 0)},  // @
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,  // A-Z
        {B(0, 0, 0, 0, 0, 0, 0, 0), B(0, 0, 0, 0, 0, 0, 0, 0), 0,
         B(0, 0, 0, 0, 0, 0, 0, 0), 0, 0, 0, B(0, 0, 0, 0, 0, 0, 0, 0), 0, 0, 0,
         B(0, 0, 0, 0, 0, 0, 0, 0)},  // [
        {B(0, 0, 0, 0, 0, 0, 0, 1), B(0, 0, 0, 0, 0, 0, 0, 0), 0,
         B(0, 0, 0, 1, 0, 0, 0, 0), 0, 0, 0, B(0, 0, 1, 0, 0, 0, 0, 0), 0, 0, 0,
         B(0, 0, 1, 0, 0, 0, 0, 0)},  // '\'
        {B(0, 0, 0, 0, 0, 0, 0, 1), B(0, 0, 0, 0, 0, 0, 0, 0), 0,
         B(0, 0, 0, 1, 0, 0, 0, 0), 0, 0, 0, B(0, 0, 1, 0, 0, 0, 0, 0), 0, 0, 0,
         B(0, 0, 1, 0, 0, 0, 0, 0)},  // ]
        {B(0, 0, 0, 0, 0, 0, 0, 0), B(0, 0, 0, 0, 0, 0, 0, 0), 0,
         B(0, 0, 0, 0, 0, 0, 0, 0), 0, 0, 0, B(0, 0, 0, 0, 0, 0, 0, 0), 0, 0, 0,
         B(0, 0, 0, 0, 0, 0, 0, 0)},  // ^
        {B(0, 0, 0, 0, 0, 0, 0, 0), B(0, 0, 0, 0, 0, 0, 0, 0), 0,
         B(0, 0, 0, 0, 0, 0, 0, 0), 0, 0, 0, B(0, 0, 0, 0, 0, 0, 0, 0), 0, 0, 0,
         B(0, 0, 0, 0, 0, 0, 0, 0)},  // _
        {B(0, 0, 0, 0, 0, 0, 0, 0), B(0, 0, 0, 0, 0, 0, 0, 0), 0,
         B(0, 0, 0, 0, 0, 0, 0, 0), 0, 0, 0, B(0, 0, 0, 0, 0, 0, 0, 0), 0, 0, 0,
         B(0, 0, 0, 0, 0, 0, 0, 0)},  // `
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,
        AL,  // a-z
        {B(0, 0, 0, 0, 0, 0, 0, 0), B(0, 0, 0, 0, 0, 0, 0, 0), 0,
         B(0, 0, 0, 0, 0, 0, 0, 0), 0, 0, 0, B(0, 0, 0, 0, 0, 0, 0, 0), 0, 0, 0,
         B(0, 0, 0, 0, 0, 0, 0, 0)},  // {
        {B(0, 0, 0, 0, 0, 0, 0, 1), B(0, 0, 0, 0, 0, 0, 0, 0), 0,
         B(0, 0, 0, 1, 0, 0, 0, 0), 0, 0, 0, B(0, 0, 1, 0, 0, 0, 0, 0), 0, 0, 0,
         B(0, 0, 1, 0, 0, 0, 0, 0)},  // |
        {B(0, 0, 0, 0, 0, 0, 0, 1), B(0, 0, 0, 0, 0, 0, 0, 0), 0,
         B(0, 0, 0, 1, 0, 0, 0, 0), 0, 0, 0, B(0, 0, 1, 0, 0, 0, 0, 0), 0, 0, 0,
         B(0, 0, 1, 0, 0, 0, 0, 0)},  // }
        {B(0, 0, 0, 0, 0, 0, 0, 1), B(0, 0, 0, 0, 0, 0, 0, 0), 0,
         B(0, 0, 0, 1, 0, 0, 0, 0), 0, 0, 0, B(0, 0, 1, 0, 0, 0, 0, 0), 0, 0, 0,
         B(0, 0, 1, 0, 0, 0, 0, 0)},  // ~
        {B(0, 0, 0, 0, 0, 0, 0, 0), B(0, 0, 0, 0, 0, 0, 0, 0), 0,
         B(0, 0, 0, 0, 0, 0, 0, 0), 0, 0, 0, B(0, 0, 0, 0, 0, 0, 0, 0), 0, 0, 0,
         B(0, 0, 0, 0, 0, 0, 0, 0)},  // DEL
};

#undef B
#undef F
#undef DI
#undef AL

COMPILE_ASSERT(WTF_ARRAY_LENGTH(asciiLineBreakTable) ==
                   asciiLineBreakTableLastChar - asciiLineBreakTableFirstChar +
                       1,
               TestLineBreakTableConsistency);

static inline bool shouldBreakAfter(UChar lastCh, UChar ch, UChar nextCh) {
  // Don't allow line breaking between '-' and a digit if the '-' may mean a
  // minus sign in the context, while allow breaking in 'ABCD-1234' and
  // '1234-5678' which may be in long URLs.
  if (ch == '-' && isASCIIDigit(nextCh))
    return isASCIIAlphanumeric(lastCh);

  // If both ch and nextCh are ASCII characters, use a lookup table for enhanced
  // speed and for compatibility with other browsers (see comments for
  // asciiLineBreakTable for details).
  if (ch >= asciiLineBreakTableFirstChar && ch <= asciiLineBreakTableLastChar &&
      nextCh >= asciiLineBreakTableFirstChar &&
      nextCh <= asciiLineBreakTableLastChar) {
    const unsigned char* tableRow =
        asciiLineBreakTable[ch - asciiLineBreakTableFirstChar];
    int nextChIndex = nextCh - asciiLineBreakTableFirstChar;
    return tableRow[nextChIndex / 8] & (1 << (nextChIndex % 8));
  }
  // Otherwise defer to the Unicode algorithm by returning false.
  return false;
}

template <bool treatNoBreakSpaceAsBreak>
inline bool needsLineBreakIterator(UChar ch) {
  if (treatNoBreakSpaceAsBreak)
    return ch > asciiLineBreakTableLastChar;
  return ch > asciiLineBreakTableLastChar && ch != noBreakSpace;
}

template <typename CharacterType, bool treatNoBreakSpaceAsBreak>
static inline int nextBreakablePosition(
    LazyLineBreakIterator& lazyBreakIterator,
    const CharacterType* str,
    unsigned length,
    int pos) {
  int len = static_cast<int>(length);
  int nextBreak = -1;

  CharacterType lastLastCh =
      pos > 1 ? str[pos - 2]
              : static_cast<CharacterType>(
                    lazyBreakIterator.secondToLastCharacter());
  CharacterType lastCh =
      pos > 0 ? str[pos - 1]
              : static_cast<CharacterType>(lazyBreakIterator.lastCharacter());
  unsigned priorContextLength = lazyBreakIterator.priorContextLength();
  for (int i = pos; i < len; i++) {
    CharacterType ch = str[i];

    if (isBreakableSpace<treatNoBreakSpaceAsBreak>(ch) ||
        shouldBreakAfter(lastLastCh, lastCh, ch))
      return i;

    if (needsLineBreakIterator<treatNoBreakSpaceAsBreak>(ch) ||
        needsLineBreakIterator<treatNoBreakSpaceAsBreak>(lastCh)) {
      if (nextBreak < i) {
        // Don't break if positioned at start of primary context and there is no
        // prior context.
        if (i || priorContextLength) {
          TextBreakIterator* breakIterator =
              lazyBreakIterator.get(priorContextLength);
          if (breakIterator) {
            nextBreak = breakIterator->following(i - 1 + priorContextLength);
            if (nextBreak >= 0) {
              nextBreak -= priorContextLength;
            }
          }
        }
      }
      if (i == nextBreak && !isBreakableSpace<treatNoBreakSpaceAsBreak>(lastCh))
        return i;
    }

    lastLastCh = lastCh;
    lastCh = ch;
  }

  return len;
}

int nextBreakablePositionIgnoringNBSP(LazyLineBreakIterator& lazyBreakIterator,
                                      int pos) {
  String string = lazyBreakIterator.string();
  if (string.is8Bit())
    return nextBreakablePosition<LChar, false>(
        lazyBreakIterator, string.characters8(), string.length(), pos);
  return nextBreakablePosition<UChar, false>(
      lazyBreakIterator, string.characters16(), string.length(), pos);
}

}  // namespace blink
